package maze;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * 用栈的方法找所有可行路径
 *
 * @author zj
 */
public class StackMethodAllPath {

    public static void main(String[] args) {
        maze(1, 1, 10, 10);
    }

    private static boolean maze(int startI, int startJ, int endI, int endJ) {
        Global.print(Global.M);

        boolean flag = false; //是否存在可行路径
        int i = 0, j = 0;
        int pathCount = 0;

        LinkedList<StackPos> stack = new LinkedList<StackPos>();

        StackPos s = new StackPos(startI, startJ, 0); // 入口进栈
        Global.M[s.i][s.j] = -1; // 进栈后标记为-1
        stack.addLast(s);

        while (!stack.isEmpty()) { //栈非空循环
            StackPos top = stack.getLast();

            if (top.i == endI && top.j == endJ) {
                pathCount++;
                System.out.print("第【" + pathCount + "】条可行路径：");
                Iterator<StackPos> it = stack.iterator();
                int count = 0;
                while (it.hasNext()) {
                    if (count % 10 == 0)
                        System.out.println();
                    StackPos temp = it.next();
                    System.out.print("(" + temp.i + "," + temp.j + ") -> ");
                    count++;
                }
                System.out.println();
                Global.print(Global.M);
                flag = true;
                StackPos s0 = stack.removeLast();
                Global.M[s0.i][s0.j] = 0;

                //如果此时栈中有元素，则要更新栈顶的next指针
                if (stack.getLast() != null) {
                    stack.getLast().next++;
                    continue;
                }

            } else { //如果不是出口
                boolean findNext = false;
                while (!findNext && top.next < 4) { //找下一个可行位置
                    switch (top.next) {
                        case 0:
                            i = top.i;
                            j = top.j + 1;
                            break;
                        case 1:
                            i = top.i - 1;
                            j = top.j;
                            break;
                        case 2:
                            i = top.i;
                            j = top.j - 1;
                            break;
                        case 3:
                            i = top.i + 1;
                            j = top.j;
                            break;
                    }
                    if (Global.M[i][j] == 0) {
                        findNext = true;
                    }
                    top.next++;
                }
                //下一个可行方位存在，则将其入栈
                if (findNext) {
                    StackPos nextS = new StackPos(i, j, 0);
                    Global.M[nextS.i][nextS.j] = -1;
                    stack.addLast(nextS);

                    //不存在可行方位，则将栈顶出栈，恢复其值
                } else {
                    StackPos ss = stack.removeLast();
                    Global.M[ss.i][ss.j] = 0;  //恢复原值，以便搜索其他路径
                }
            }
        }
        if (!flag) {
            System.out.println("未找到可行路径");
        }
        return flag;
    }


}
